package LC;

/**
 * https://leetcode.com/problems/search-a-2d-matrix/description/
 * Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
 * Integers in each row are sorted from left to right.
 * The first integer of each row is greater than the last integer of the previous row.
 * For example,
 * Consider the following matrix:
 * [
 * [1,   3,  5,  7],
 * [10, 11, 16, 20],
 * [23, 30, 34, 50]
 * ]
 * Given target = 3, return true.
 */
public class LC_074_Searcha2D_Matrix_BinarySearch {
    public static void main(String[] args) {
        int[][] a = {
                {1, 3, 5, 7},
                {10, 11, 16, 20},
                {23, 30, 34, 50}
        };
        System.out.println(Solution.searchMatrix(a, 16));
    }

    static class Solution {
        static boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
                return false;
            int l = 0;
            int r = matrix.length - 1;

            while (l <= r) {
                int mid = (l + r) >> 1;
                if (matrix[mid][0] == target)
                    return true;
                if (matrix[mid][0] > target)
                    r = mid - 1;
                else
                    l = mid + 1;
            }

            int row = r;
            if (row < 0)
                return false;
            l = 0;
            r = matrix[0].length - 1;

            while (l <= r) {
                int mid = (l + r) >> 1;
                if (matrix[row][mid] == target)
                    return true;
                if (matrix[row][mid] > target)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            return false;
        }
    }
}
